package Midium;
//18.四数之和

import java.util.*;

public class Solution18 {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        Set<List<Integer>> set = new HashSet<>();
        //-2 -1 0 0 1 2 target:0
        // i  k     m j          直接找到[-2,-1,1,2] => k++,m-- =>找到[-2,0,0,1] => k++,m-- =>循环结束
        //    i k   m j  因为2>0 所以m--  => -1 0 0 2 => m-- =>循环结束，j--,m=j-1 =>-1 0 0 1 找到了
        for (int i = 0; i < nums.length - 3; i++) {
            int a = nums[i];
            for (int j = nums.length - 1; j > i + 2; j--) {
                int k = i+1,m=j-1;
                int b = nums[j];
                while (k<m){
                    int c = nums[k];
                    int d = nums[m];
                    if(a+b+c+d == target){
                        List<Integer> list = new ArrayList<>();
                        list.add(a);list.add(b);list.add(c);list.add(d);
                        set.add(list);
                        while (nums[k]==nums[k+1] && k < m){
                            k++;
                        }
                        while (nums[m]==nums[m-1] && k < m){
                            m--;
                        }
                        k++;m--;
                    }
                    else if(a+b+c+d > target){
                        while (nums[m]==nums[m-1] && k < m){
                            m--;
                        }
                        m--;
                    }
                    else {
                        while (nums[k]==nums[k+1] && k < m){
                            k++;
                        }
                        k++;
                    }
                }
            }
        }
        return new ArrayList<>(set);
    }

    public static void main(String[] args) {
        Solution18 s18 = new Solution18();
        s18.fourSum(new int[]{-2,-1,-1,1,1,2,2},0);
    }
}
